8.1 冒泡排序

冒泡排序是一种简单且直观的排序算法。它的基本思想是通过多次遍历待排序的序列。

每次比较相邻的两个元素，如果它们的顺序不正确（例如，第一个比第二个大），就交换它们的位置。

经过多次这样的操作，较大的元素会逐渐“冒泡”到序列的末端。

本节代码存放目录为 lesson16

概念与原理

冒泡排序的原理如下：

• 从序列的起始位置开始，逐对比较相邻的元素。

• 如果第一个元素比第二个大，就交换它们。

• 继续比较相邻元素，直到序列末尾，最大值会被冒泡到序列的末端。

• 重复步骤 1-3，直到整个序列有序。

冒泡排序是一种稳定的排序算法，即当两个元素相等时，它们的顺序不会改变。

冒泡排序的步骤示例

给定如下无序数组，按照从小到大排序：

[5, 3, 8, 4, 2]

通过冒泡排序的步骤如下：

第一轮：

比较 arr[0] 与 arr[1]，5 与 3 比较，交换：[5, 3, 8, 4, 2] -> [3, 5, 8, 4, 2]

比较 arr[1] 与 arr[2]，5 与 8 比较，不交换：[3, 5, 8, 4, 2] -> [3, 5, 8, 4, 2]

比较 arr[2] 与 arr[3]，8 与 4 比较，交换：[3, 5, 8, 4, 2] -> [3, 5, 4, 8, 2]

比较 arr[3] 与 arr[4]，8 与 2 比较，交换：[3, 5, 4, 8, 2] -> [3, 5, 4, 2, 8]

经过第一轮，最大的一个数组已经被移动到了最后的位置，也就是：8 目前在最后一位了。

第二轮：

比较 arr[0] 与 arr[1]，3 与 5 比较，不交换：[3, 5, 4, 2, 8] -> [3, 5, 4, 2, 8]

比较 arr[1] 与 arr[2]，5 与 4 比较，交换：[3, 5, 4, 2, 8] -> [3, 4, 5, 2, 8]

比较 arr[2] 与 arr[3]，5 与 2 比较，交换：[3, 4, 5, 2, 8] -> [3, 4, 2, 5, 8]

经过第二轮，后面两位都已经排列好了。

第三轮：

比较 arr[0] 与 arr[1]，3 与 4 比较，不交换：[3, 4, 2, 5, 8] -> [3, 4, 2, 5, 8]

比较 arr[1] 与 arr[2]，4 与 2 比较，交换：[3, 2, 4, 5, 8] -> [3, 2, 4, 5, 8]

经过第三轮，后面三位都已经排列好了。

第四轮：

比较 arr[0] 与 arr[1]，3 与 2 比较，交换：[3, 2, 4, 5, 8] -> [2, 3, 4, 5, 8]

至此，冒泡排序已经完成，经过四轮冒泡，10 次比较最终得出了结果。

总的来说，冒泡排序就是经过 n - 1轮，从 arr[0] 一直到 arr[n -1] 进行逐个比较，最后将数组都按照序列规则排列。

冒泡排序的时间复杂度如下所示：

• 最坏情况：O(n²)，即数组本身是反序排列的。

• 最好情况：O(n)，即数组已经是有序的。

• 平均情况：O(n²)，即数组是随机排列的。

冒泡排序时间复杂度较高，但它简单易懂，比较适合用于我们的学习理解。

Go语言的实现

接下来我们使用 Go 语言实现一个冒泡排序算法：

func bubbleSort(arr []int) {
    length := len(arr)
    num := 0

    // 轮次控制
    for i := 0; i < length-1; i++ {
        fmt.Printf("\n第 %d 轮\n", i+1)

        // 比较次数控制
        for j := 0; j < length-i-1; j++ {
            num++
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
            fmt.Printf("第 %d 次比较，结果: %v\n", num, arr)
        }
    }
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    bubbleSort(arr)
    fmt.Println("排序结果: ", arr)
}

执行结果如下所示：

第 1 轮
第 1 次比较，结果: [3 5 8 4 2]
第 2 次比较，结果: [3 5 8 4 2]
第 3 次比较，结果: [3 5 4 8 2]
第 4 次比较，结果: [3 5 4 2 8]

第 2 轮
第 5 次比较，结果: [3 5 4 2 8]
第 6 次比较，结果: [3 4 5 2 8]
第 7 次比较，结果: [3 4 2 5 8]

第 3 轮
第 8 次比较，结果: [3 4 2 5 8]
第 9 次比较，结果: [3 2 4 5 8]

第 4 轮
第 10 次比较，结果: [2 3 4 5 8]
排序结果:  [2 3 4 5 8]

代码优化

冒泡排序可以通过提前判断是否已经有序来优化。如果在一轮排序过程中没有发生任何交换操作，说明数组已经是有序的，可以提前结束排序。

如下代码所示：

func bubbleSortOpm(arr []int) {
    length := len(arr)
    num := 0

    // 轮次控制
    for i := 0; i < length-1; i++ {
        fmt.Printf("\n第 %d 轮\n", i+1)

        // 此次是否进行过交换
        swapped := false

        // 比较次数控制
        for j := 0; j < length-i-1; j++ {
            num++
            if arr[j] > arr[j+1] {
                swapped = true
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
            fmt.Printf("第 %d 次比较，结果: %v\n", num, arr)
        }

        // 如果没有发生交换，说明数组已经有序，提前退出
        if !swapped {
            break
        }
    }
}

在上面的代码中，我们增加了 swapped 参数，当前轮次元素顺序没有更新时，那么说明已经排序好了，就没有必要再往下走了。

小结

本节我们讲解了冒泡排序的基本原理、步骤示例和 Go 语言的实现。

关于本节总结如下：

• 时间复杂度：最坏情况下为 O(n²)，最好情况下为 O(n)。

• 稳定性：冒泡排序是稳定的排序算法。

• 应用场景：由于其简单性，冒泡排序主要用于学习和小型数据集的排序，不适用于大型数据集的排序。